package com.yangzhe.algorithm.c014;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ConvertQueueAndStack {

    class MyQueue {
        /**
         * in栈负责入队列
         */
        public Stack<Integer> in = new Stack<>();
        /**
         * out栈是in栈的逆序，负责出队列
         * out为空时，in全部出栈到out中
         */
        public Stack<Integer> out = new Stack<>();

        public MyQueue() {

        }

        /**
         * 将元素 x 推到队列的末尾
         *
         * @param x
         */
        public void push(int x) {
            in.push(x);
        }

        /**
         * 从队列的开头移除并返回元素
         *
         * @return
         */
        public int pop() {
            if (out.isEmpty()) {
                inToOut();
            }
            return out.pop();
        }

        /**
         * 返回队列开头的元素
         *
         * @return
         */
        public int peek() {
            if (out.isEmpty()) {
                inToOut();
            }
            return out.peek();
        }

        /**
         * 如果队列为空
         *
         * @return
         */
        public boolean empty() {
            return in.isEmpty() && out.isEmpty();
        }

        /**
         * 将in栈弹出并入栈到out
         */
        private void inToOut() {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    /**
     * https://leetcode.cn/problems/implement-stack-using-queues/
     */
    class MyStack {

        /**
         * 队列每次入队新元素后，都把新元素之前的元素弹出再入队，这样顺序就和栈一致了
         */
        public Queue<Integer> queue = new LinkedList<>();

        public MyStack() {

        }

        /**
         * 将元素 x 压入栈顶
         * @param x
         */
        public void push(int x) {
            int size = queue.size();
            queue.offer(x);
            // 把新值之前的值都重新入队，这样相当于逆序，出对时和栈的顺序就一致了
            for (int i = 0; i < size; i++) {
                queue.offer(queue.poll());
            }
        }

        /**
         * 移除并返回栈顶元素
         * @return
         */
        public int pop() {
            return queue.poll();
        }

        /**
         * 返回栈顶元素
         * @return
         */
        public int top() {
            return queue.peek();
        }

        /**
         * 如果栈是空的，返回 true ；否则，返回 false
         * @return
         */
        public boolean empty() {
            return queue.isEmpty();
        }
    }


}
